/*
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
* */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var removeNthFromEnd = function (head, n) {
  if(!head) return null;

  // 定义虚拟头节点
  let ret = new ListNode(-1, head);

  //让第一个指针先走
  let front = ret;
  while (n--){ // n-- 是先比 再减 //比如我们要删除倒数第3个节点 我们先让双指针中的一个先走3次 0（虚拟头）--1--2--3 ， 这样我们的after节点指向的就是要删除的倒数第n个节点的前一个
    front = front.next;
  }

  let after = ret;
  while (front.next){
    after = after.next;
    front = front.next;
  }
  // 此时after指向倒数第n个节点的前一个节点
  after.next = after.next.next;

  return ret.next;
}

var removeNthFromEnd = function (head, n) {
  let fast, slow;
  fast = slow = head;
  // 快指针先前进 n 步
  while (n-- > 0) {
    fast = fast.next;
  }
  if (fast == null) {
    // 如果此时快指针走到头了，
    // 说明倒数第 n 个节点就是第一个节点
    return head.next;
  }
  // 让慢指针和快指针同步向前
  while (fast != null && fast.next != null) {
    fast = fast.next;
    slow = slow.next;
  }
  // slow.next 就是倒数第 n 个节点，删除它
  slow.next = slow.next.next;
  return head;
};
